class Solution {
  public:
    int largestRectangleArea(vector<int> &h) {
        stack<int> S;
        h.push_back(0);
        int sum = 0;
        for (int i = 0; i < h.size(); i++) {
            if (S.empty() || h[i] > h[S.top()])
                S.push(i);
            else {
                int tmp = S.top();
                S.pop();
                sum = max(sum, h[tmp] * (S.empty() ? i : i - S.top() - 1));
                i--;
            }
        }
        return sum;
    }

    int maximalRectangle(vector<vector<char>> &matrix) {
        if (matrix.size() == 0 || matrix[0].size() == 0) {
            return 0;
        }
        int maxArea = 0;
        vector<int> height(matrix[0].size(), 0);
        for (int i = 0; i < matrix.size(); ++i) {
            for (int j = 0; j < matrix[0].size(); ++j) {
                height[j] = matrix[i][j] == '0' ? 0 : height[j] + 1;
            }
            maxArea = std::max(largestRectangleArea(height), maxArea);
        }
        return maxArea;
    }
};